Search Results

Documents authored by Paperman, Charles

Document
DOI: 10.4230/LIPIcs.STACS.2023.51
An Algebraic Approach to Vectorial Programs

Authors: Charles Paperman, Sylvain Salvati, and Claire Soyez-Martin

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Vectorial programming, the combination of SIMD instructions with usual processor instructions, is known to speed-up many standard algorithms. Simple regular languages have benefited from this technology. This paper is a first step towards pushing these benefits further. We take advantage of the inner algebraic structure of regular languages and produce high level representations of efficient vectorial programs that recognize certain classes of regular languages. As a technical ingredient, we establish equivalences between classes of vectorial circuits and logical formalisms, namely unary temporal logic and first order logic. The main result is the construction of compilation procedures that turns syntactic semigroups into vectorial circuits. The circuits we obtain are small in that they improve known upper-bounds on representations of automata within the logical formalisms. The gain is mostly due to a careful sharing of sub-formulas based on algebraic tools.
Cite as

Charles Paperman, Sylvain Salvati, and Claire Soyez-Martin. An Algebraic Approach to Vectorial Programs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{paperman_et_al:LIPIcs.STACS.2023.51,
  author =	{Paperman, Charles and Salvati, Sylvain and Soyez-Martin, Claire},
  title =	{{An Algebraic Approach to Vectorial Programs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{51:1--51:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.51},
  URN =		{urn:nbn:de:0030-drops-177030},
  doi =		{10.4230/LIPIcs.STACS.2023.51},
  annote =	{Keywords: Automata theory, Semigroups, Vectorisation}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.116
Dynamic Membership for Regular Languages

Authors: Antoine Amarilli, Louis Jachiet, and Charles Paperman

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under letter substitutions on w. We consider this problem on the unit cost RAM model with logarithmic word length, where the problem always has a solution in O(log|w| / log log|w|) per operation. We show that the problem is in O(log log|w|) for languages in an algebraically-defined, decidable class QSG, and that it is in O(1) for another such class QLZG. We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require Ω(log|w| /log log|w|) operations in the worst case; and that QSG languages not in QLZG admit a reduction from the prefix problem for the multiplicative monoid U₁ = {0, 1}, which we conjecture cannot be maintained in O(1). This yields a conditional trichotomy. We also investigate intermediate cases between O(1) and O(log log|w|). Our results are shown via the dynamic word problem for monoids and semigroups, for which we also give a classification. We thus solve open problems of the paper of Skovbjerg Frandsen, Miltersen, and Skyum [Skovbjerg Frandsen et al., 1997] on the dynamic word problem, and additionally cover regular languages.
Cite as

Antoine Amarilli, Louis Jachiet, and Charles Paperman. Dynamic Membership for Regular Languages. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ICALP.2021.116,
  author =	{Amarilli, Antoine and Jachiet, Louis and Paperman, Charles},
  title =	{{Dynamic Membership for Regular Languages}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{116:1--116:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.116},
  URN =		{urn:nbn:de:0030-drops-141850},
  doi =		{10.4230/LIPIcs.ICALP.2021.116},
  annote =	{Keywords: regular language, membership, RAM model, updates, dynamic}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.117
On Polynomial Recursive Sequences

Authors: Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is b_n = n!. Our main result is that the sequence u_n = nⁿ is not polynomial recursive.
Cite as

Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues. On Polynomial Recursive Sequences. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 117:1-117:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cadilhac_et_al:LIPIcs.ICALP.2020.117,
  author =	{Cadilhac, Micha\"{e}l and Mazowiecki, Filip and Paperman, Charles and Pilipczuk, Micha{\l} and S\'{e}nizergues, G\'{e}raud},
  title =	{{On Polynomial Recursive Sequences}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{117:1--117:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.117},
  URN =		{urn:nbn:de:0030-drops-125240},
  doi =		{10.4230/LIPIcs.ICALP.2020.117},
  annote =	{Keywords: recursive sequences, expressive power, weighted automata, higher-order pushdown automata}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.115
Topological Sorting with Regular Constraints

Authors: Antoine Amarilli and Charles Paperman

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We introduce the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological sort that forms a word in K. This natural problem applies to several settings, e.g., scheduling with costs or verifying concurrent programs. We consider the problem CTS[K] where the target language K is fixed, and study its complexity depending on K. We show that CTS[K] is tractable when K falls in several language families, e.g., unions of monomials, which can be used for pattern matching. However, we show that CTS[K] is NP-hard for K = (ab)^* and introduce a shuffle reduction technique to show hardness for more languages. We also study the special case of the constrained shuffle problem (CSh), where the input graph is a disjoint union of strings, and show that CSh[K] is additionally tractable when K is a group language or a union of district group monomials. We conjecture that a dichotomy should hold on the complexity of CTS[K] or CSh[K] depending on K, and substantiate this by proving a coarser dichotomy under a different problem phrasing which ensures that tractable languages are closed under common operators.
Cite as

Antoine Amarilli and Charles Paperman. Topological Sorting with Regular Constraints. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ICALP.2018.115,
  author =	{Amarilli, Antoine and Paperman, Charles},
  title =	{{Topological Sorting with Regular Constraints}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{115:1--115:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.115},
  URN =		{urn:nbn:de:0030-drops-91193},
  doi =		{10.4230/LIPIcs.ICALP.2018.115},
  annote =	{Keywords: Topological sorting, shuffle problem, regular language}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.115
Continuity and Rational Functions

Authors: Michaël Cadilhac, Olivier Carton, and Charles Paperman

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A word-to-word function is continuous for a class of languages V if its inverse maps V languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes. Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages. Previous algebraic studies of transducers have focused on the structure of the underlying input automaton, disregarding the output. We propose a comparison of the two algebraic approaches through two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?
Cite as

Michaël Cadilhac, Olivier Carton, and Charles Paperman. Continuity and Rational Functions. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cadilhac_et_al:LIPIcs.ICALP.2017.115,
  author =	{Cadilhac, Micha\"{e}l and Carton, Olivier and Paperman, Charles},
  title =	{{Continuity and Rational Functions}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{115:1--115:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.115},
  URN =		{urn:nbn:de:0030-drops-74583},
  doi =		{10.4230/LIPIcs.ICALP.2017.115},
  annote =	{Keywords: Transducers, rational functions, language varieties, continuity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.117
Regular Separability of Parikh Automata

Authors: Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We investigate a subclass of languages recognized by vector addition systems, namely languages of nondeterministic Parikh automata. While the regularity problem (is the language of a given automaton regular?) is undecidable for this model, we surprisingly show decidability of the regular separability problem: given two Parikh automata, is there a regular language that contains one of them and is disjoint from the other? We supplement this result by proving undecidability of the same problem already for languages of visibly one counter automata.
Cite as

Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman. Regular Separability of Parikh Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 117:1-117:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.ICALP.2017.117,
  author =	{Clemente, Lorenzo and Czerwinski, Wojciech and Lasota, Slawomir and Paperman, Charles},
  title =	{{Regular Separability of Parikh Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{117:1--117:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.117},
  URN =		{urn:nbn:de:0030-drops-74971},
  doi =		{10.4230/LIPIcs.ICALP.2017.117},
  annote =	{Keywords: Regular separability problem, Parikh automata, integer vector addition systems, visible one counter automata, decidability, undecidability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.24
Separability of Reachability Sets of Vector Addition Systems

Authors: Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Given two families of sets F and G, the F-separability problem for G asks whether for two given sets U, V in G there exists a set S in F, such that U is included in S and V is disjoint with S. We consider two families of sets F: modular sets S which are subsets of N^d, defined as unions of equivalence classes modulo some natural number n in N, and unary sets, which extend modular sets by requiring equality below a threshold n, and equivalence modulo n above n. Our main result is decidability of modular- and unary-separability for the class G of reachability sets of Vector Addition Systems, Petri Nets, Vector Addition Systems with States, and for sections thereof.
Cite as

Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman. Separability of Reachability Sets of Vector Addition Systems. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.STACS.2017.24,
  author =	{Clemente, Lorenzo and Czerwinski, Wojciech and Lasota, Slawomir and Paperman, Charles},
  title =	{{Separability of Reachability Sets of Vector Addition Systems}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.24},
  URN =		{urn:nbn:de:0030-drops-70091},
  doi =		{10.4230/LIPIcs.STACS.2017.24},
  annote =	{Keywords: separability, Petri nets, modular sets, unary sets, decidability}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.616
Finite-Degree Predicates and Two-Variable First-Order Logic

Authors: Charles Paperman

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature. Replacing finite-degree by arbitrary numerical predicates in the statement would entail a long standing conjecture on the circuit complexity of the addition function. Thus, this result can be viewed as a uniform version of this circuit lower bound.
Cite as

Charles Paperman. Finite-Degree Predicates and Two-Variable First-Order Logic. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 616-630, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{paperman:LIPIcs.CSL.2015.616,
  author =	{Paperman, Charles},
  title =	{{Finite-Degree Predicates and Two-Variable First-Order Logic}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{616--630},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.616},
  URN =		{urn:nbn:de:0030-drops-54420},
  doi =		{10.4230/LIPIcs.CSL.2015.616},
  annote =	{Keywords: First order logic, automata theory, semigroup, modular predicates}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.329
Two-variable first order logic with modular predicates over words

Authors: Luc Dartois and Charles Paperman

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We consider first order formulae over the signature consisting of the symbols of the alphabet, the symbol < (interpreted as a linear order) and the set MOD of modular numerical predicates. We study the expressive power of FO^2[<,MOD], the two-variable first order logic over this signature, interpreted over finite words. We give an algebraic characterization of the corresponding regular languages in terms of their syntactic morphisms and we also give simple unambiguous regular expressions for them. It follows that one can decide whether a given regular language is captured by FO^2[<,MOD]. Our proofs rely on a combination of arguments from semigroup theory (stamps), model theory (Ehrenfeucht-Fraïssé games) and combinatorics.
Cite as

Luc Dartois and Charles Paperman. Two-variable first order logic with modular predicates over words. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 329-340, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{dartois_et_al:LIPIcs.STACS.2013.329,
  author =	{Dartois, Luc and Paperman, Charles},
  title =	{{Two-variable first order logic with modular predicates over words}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{329--340},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.329},
  URN =		{urn:nbn:de:0030-drops-39450},
  doi =		{10.4230/LIPIcs.STACS.2013.329},
  annote =	{Keywords: First order logic, automata theory, semigroup, modular predicates}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact